package com.tarry.sort;

import java.util.Arrays;

/**
 * 归并排序 <br>
 * <p>
 * 采用分而治之的思想，结合归并实现
 * </p>
 * <br>
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = new int[]{10, 7, 8, 9, 1, 5};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] array) {
        mergeSortInternally(array, 0, array.length - 1);
    }

    private static void mergeSortInternally(int[] array, int left, int right) {
        if (left >= right) {
            // 当左边 == 右边时，说明数组不能再进行被分割
            return;
        }

        // 计算中间值
        int middle = left + (right - left) / 2;
        mergeSortInternally(array, left, middle);
        mergeSortInternally(array, middle + 1, right);
//        merge(array, left, middle, right);
        mergeBySentry(array, left, middle, right);
    }

    /**
     * 普通归并
     */
    private static void merge(int[] array, int left, int middle, int right) {
        // 左边数组起始下标
        int leftIndex = left;
        // 右边数组起始下标
        int rightIndex = middle + 1;
        // 临时数组起始下标
        int tmpIndex = 0;
        // 初始化一个大小相同的临时数组
        int[] tmpArray = new int[right - left + 1];
        while (leftIndex <= middle && rightIndex <= right) {
            // 比较两个数组的初始值，较小的元素放在临时数组的第一位
            if (array[leftIndex] <= array[rightIndex]) {
                tmpArray[tmpIndex++] = array[leftIndex++];
            } else {
                tmpArray[tmpIndex++] = array[rightIndex++];
            }
        }

        /*
          由于分裂出的数组，最终长度可能不一样，导致一个数组先遍历完成，另一个数组还未进行数据比较，
          此时直接将未进行比较的数组数据添加到临时数组即可
         */
        // 初始化下标,先将下标初始化为左半部分的数组
        int start = leftIndex;
        int end = middle;
        //说明右半部分未比较完,此时将下标再重置为右半部分的数组
        if (rightIndex <= right) {
            start = rightIndex;
            end = right;
        }

        //将未比较完的有序数组直接添加到临时数组中
        while (start <= end) {
            tmpArray[tmpIndex++] = array[start++];
        }

        //将临时数组的数据拷贝到原数组中
        if (right - left + 1 >= 0)
            System.arraycopy(tmpArray, 0, array, left, right - left + 1);
    }

    /**
     * 結合哨兵思想的归并
     */
    private static void mergeBySentry(int[] array, int left, int middle, int right) {
        // 初始化左边数组对应临时空间，并增加一个哨兵位置
        int[] leftArray = new int[middle - left + 2];
        // 初始化右边数组对应临时空间，并增加一个哨兵位置 right - （middle + 1） + 1
        int[] rightArray = new int[right - middle + 1];

        // 将原数组拷贝到临时数组
        if (middle - left + 1 >= 0)
            System.arraycopy(array, left, leftArray, 0, leftArray.length - 1);

        // 为左边数组增加哨兵
        leftArray[middle - left + 1] = Integer.MAX_VALUE;

        // 将原数组拷贝到右边临时数组
        if (right - middle > 0)
            System.arraycopy(array, middle + 1, rightArray, 0, rightArray.length - 1);

        // 为右边数组增加哨兵
        rightArray[right - middle] = Integer.MAX_VALUE;

        int leftIndex = 0;
        int rightIndex = 0;
        int tmpIndex = left;

        // 左节点小于右节点时,将排好序的临时空间数据加入到原数组中,当leftIndex到达哨兵节点时,leftIndex不再增加,只增加rightIndex即可.
        while (tmpIndex <= right) {
            if (leftArray[leftIndex] <= rightArray[rightIndex]) {
                array[tmpIndex++] = leftArray[leftIndex++];
            } else {
                array[tmpIndex++] = rightArray[rightIndex++];
            }
        }
    }

}
